//
//  SGHTreeNode.m
//  ObjectiveCDemo20200321
//
//  Created by 远平 on 2021/11/25.
//  Copyright © 2021 远平. All rights reserved.
//

#import "SGHTreeNode.h"

struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

@implementation SGHTreeNode

//来自：[iOS面试题合集（数据结构篇）](https://mp.weixin.qq.com/s/MRj6_R5tkC_AJ3fncnTzVQ)
- (void)test {
    struct TreeNode *head = constructTree(true);
    if (IsBalanced(head)) {
        printf("isBal = yes\n");
    } else {
        printf("isBal = no\n");
    }
    
    struct TreeNode *head2 = constructTree(false);
    if (IsBalanced(head2)) {
        printf("isBal2 = yes\n");
    } else {
        printf("isBal2 = no\n");
    }
}

int TreeDepth(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftD = TreeDepth(root->left);
    int rightD = TreeDepth(root->right);
    return (leftD > rightD) ? (leftD + 1) : (rightD + 1);
}

bool IsBalanced(struct TreeNode *root) {
    if (root == NULL) {
        return true;
    }
    int leftD = TreeDepth(root->left);
    int rightD = TreeDepth(root->right);
    int diff = leftD - rightD;
    if (diff > 1 || diff < -1) {
        return false;
    }
    return IsBalanced(root->left) && IsBalanced(root->right);
}

//构造一个平衡二叉树
/*
        23
       /   \
      1     9
     / \   /  \
    18 15 31   40
      /  \
     25   3
 */
struct TreeNode * constructTree(bool isBalanced) {
    struct TreeNode *tree23 = buildNodeWith(23);
    struct TreeNode *tree1 = buildNodeWith(1);
    struct TreeNode *tree9 = buildNodeWith(9);
    struct TreeNode *tree18 = buildNodeWith(18);
    struct TreeNode *tree15 = buildNodeWith(15);
    struct TreeNode *tree31 = buildNodeWith(31);
    struct TreeNode *tree40 = buildNodeWith(40);
    struct TreeNode *tree25 = buildNodeWith(25);
    struct TreeNode *tree3 = buildNodeWith(3);
    
    tree23->left = tree1;
    tree23->right = tree9;
    
    tree1->left = tree18;
    tree1->right = tree15;
    
    tree9->left = tree31;
    tree9->right = tree40;
    
    tree15->left = tree25;
    if (isBalanced) {
        tree15->right = tree3;
    } else {
        tree25->right = tree3;
    }
    
    return tree23;
}
//构建一个Node
struct TreeNode *buildNodeWith(int value) {
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}


@end
